perm filename TEST.TEX[TEX,DEK]1 blob
sn#356211 filedate 1978-05-24 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \input ACPhdr % 1
C00019 ENDMK
C⊗;
\input ACPhdr % 1
%Example TEX input related to Seminumerical Algorithms % 2
\setcpage 1 % 3
\titlepage %This tells the page format routine not to put a page number on top % 4
\runninglefthead{RANDOM NUMBERS} \corners % 5
\hjust{\def\\{\hskip 1pt}\:=C\\H\\A\\P\\T\\E\\R\hskip 10 pt T\\H\\R\\E\\E} % 6
\vskip 1 cm plus 30 pt minus 10 pt % 7
\rjustline{\:; RANDOM NUMBERS} % 8
\vskip .5 cm plus 1 pc minus 5 pt % 9
\quoteformat{Anyone who considers arithmetical\cr %10
methods of producing random digits\cr is, of course, %11
in a state of sin.\cr} author{JOHN VON NEUMANN (1951)} %12
\quoteformat{Round numbers are always false.\cr} %13
author{SAMUEL JOHNSON (c. 1750)} %14
\vskip 1 cm plus 1 pc minus 5 pt %15
\runningrighthead{INTRODUCTION} section{3.1} %16
\sectionbegin{3.1. %17
INTRODUCTION} %18
Numbers which are ``chosen at random'' are useful in a wide variety of %19
applications. For example: %20
% This blank line specifies end of paragraph %21
\yskip % This means a bit of extra space between paragraphs %22
\textindent{a)}{\sl Simulation.}\xskip When a computer is used to simulate %23
natural phenomena, random numbers are required to make things realistic. %24
Simulation covers many fields, from the study of nuclear physics (where %25
particles are subject to random collisions) to systems engineering (where %26
people come into, say, a bank at random intervals).\par %27
\yskip\textindent{b)}{\sl Sampling.}\xskip It is often impractical to examine %28
all cases, but a random sample will provide insight into what constitutes %29
``typical'' behavior. %30
%31
\yskip It is not easy to invent a foolproof random-number generator. This fact %32
was convincingly impressed upon the author several years ago, when he attempted %33
to create a fantastically good random-number generator using the following %34
peculiar method: %35
%36
\algbegin Algorithm K (``Super-random'' number %37
generator). Given a 10-digit decimal number $X$, this algorithm may be %38
used to change $X$ to the number which should come next in a supposedly random %39
sequence.\par %40
\algstep K1. [Choose number of iterations.] Set $Y←\lfloor X/10↑9 \rfloor$, %41
i.e., the most significant digit of $X$. (We will execute steps K2 through K13, %42
which cause $X$ to be transformed in various weird and wonderful ways,
$Y+1$ times; that is, we will randomize the digits a {\sl random} number of %43
times.)\par %44
\algstep K10. [99999 modify.] If $X<10↑5$, set $X←X↑2 + 99999$; %45
otherwise set $X←X-99999$.\xskip\blackslug\par\yyskip %46
%47
\topinsert{\tablehead{Table 1} %48
\def\fl{\hskip 0pt plus 1000cm minus 1000cm}
\hjust to size{\fl A COLOSSAL COINCIDENCE: THE NUMBER 6065038420\fl} %49
\hjust to size{\fl IS TRANSFORMED INTO ITSELF BY ALGORITHM K.\fl} %50
\vskip 4 pt \hrule %51
\hjust to size{\fl\valign{\vskip 6pt#\vfill\vskip 6pt\cr %52
\halign{\lft{#}\qquad⊗\ctr{#}⊗\qquad\lft{$#$}\cr %53
Step⊗$X$ (after)\cr %54
\noalign{\vskip 10 pt \vfill} %55
K1⊗6065038420\cr K12⊗1905867781⊗Y=5\cr} %end of \halign on line 53 %56
\cr %end of first column to be \valigned %57
\noalign{\qquad\vrule\qquad} %vertical rule between columns %58
\halign{\lft{#}\qquad⊗\ctr{#}⊗\qquad\lft{$#$}\cr %59
Step⊗$X$ (after)\cr %60
\noalign{\vskip 10 pt \vfill} %61
K10⊗1620063735\cr %62
K11⊗1620063735\cr K12⊗6065038420⊗Y=0\cr}%end of \halign on line 59 %63
\cr}\fl} %end of 2nd \valigned column,\hjust %64
\hrule} %end of the \topinsert on line 48 %65
The moral to this story is that {\sl random numbers should not be %66
generated with a method chosen at random.} Some theory should be used. %67
%68
\exbegin{EXERCISES} %69
\trexno 1. [20] Suppose that you wish to obtain a decimal digit at random, not %70
using a computer. Shifting to exercise 16, let $f(x,y)$ be a function such that %71
if $0≤x,y<m$, then $0≤f(x,y)<m$. The sequence is constructed by selecting %72
$X↓0$ and $X↓1$ arbitrarily, and then letting$$ %73
X↓{n+1} = f(X↓n,X↓{n-1}) \qquad \hjust{for} \qquad n>0.$$ %74
What is the maximum period conceivably attainable in this case? %75
%76
\exno 17. [10] Generalize the situation in the previous exercise so that %77
$X↓{n+1}$ depends on the preceding $k$ values of the sequence. %78
\par\vskip 0pt plus 100 cm\eject %79
\runningrighthead{GENERATING UNIFORM RANDOM NUMBERS} section{3.2} %80
\sectionbegin{3.2. GENERATING UNIFORM RANDOM NUMBERS} %81
In this section we shall consider methods for generating a sequence of random %82
fractions, i.e., random {\sl real numbers $U↓n$, uniformly distributed %83
between zero and one.} Since a computer can represent a real number with only %84
finite accuracy, we shall actually be generating integers $X↓n$ between %85
zero and some number $m$; the fraction$$U↓n = X↓n/m \eqno(1)$$ will %86
then lie between zero and one. %87
%88
\vskip.4in plus.2in minus.2in %89
\runningrighthead{THE LINEAR CONGRUENTIAL METHOD} section{3.2.1} %90
\sectionbegin{3.2.1. The Linear Congruential Method} %91
By far the most successful random number generators known today are special %92
cases of the following scheme, introduced by D. H. Lehmer in 1948. [See %93
{\sl Annals Harvard Comp. Lab.} {\bf 26}(1951), 141-146.] We choose four %94
``magic numbers'':$$ %95
\vcenter{\halign{\rt{$#$}⊗\lft{\quad#}⊗\quad\rt{$#$}⊗\lft{$\;#$}\cr %96
X↓0,⊗the starting value;⊗X↓0⊗≥0.\cr %97
m,⊗the modulus;⊗m⊗>X↓0,\quad m>a,\quad m>c.\cr}}\eqno(1)$$ %98
The desired sequence of random numbers $\langle X↓n \rangle$ is then %99
obtained by setting$$X↓{n+1}=(aX↓n+c)\mod m,\qquad n≥0.\eqno(2)$$This is %100
called a {\sl linear congruential sequence.} %101
%102
Let $w$ be the computer's word size. The following program computes $(aX+c) %103
\mod(w+1)$ efficiently:$$\vcenter{\mixfour{ %104
01⊗⊗LDAN⊗X⊗$\rA←-X.$\cr %105
02⊗⊗MUL⊗A⊗$\rAX ← (\rA)\cdot a.$\cr %106
03⊗⊗STX⊗TEMP\cr 05⊗⊗JANN⊗*+3⊗Exit if $\rA≥0.$\cr %107
07⊗⊗ADD⊗=$w$-1=⊗\qquad\blackslug\cr}}\eqno(2↑\prime)$$ %108
\par\proofbegin We have $x=1+qp↑e$ for some integer $q$ which is not a %109
multiple of $p$. By the binomial formula$$ %110
\eqalign{x↑p⊗=1+{p\choose 1}qp↑e+\cdots+{p\choose{p-1}}q↑{p-1} %111
p↑{(p-1)e}+q↑p p↑{pe}\cr %112
⊗=1+qp↑{e+1}\left(1+{1\over p}{p\choose 2}qp↑e + {1\over p} %113
{p\choose 3}q↑2 p↑{2e}+\cdots+{1\over p}{p\choose p}q↑{p-1} %114
p↑{(p-1)e}\right).\cr}$$ By repeated application of Lemma P, we find that %115
$$\eqalign{(a↑{p↑g} - 1)/(a-1)⊗≡ 0 \modulo %116
{p↑g},\cr(a↑{p↑g}-1)/(a-1)⊗\neqv 0 \modulo{p↑{g+1}}.\cr}\eqno(6)$$ %117
If $1<k<p$, $p\choose k$ is divisible by $p$. \biglp{\sl Note:}\xskip A %118
generalization of this result appears in exercise 3.2.2-11(a).\bigrp\ By %119
Euler's theorem (exercise 1.2.4-48), $a↑{\varphi(p↑{e-f})}≡ 1 \modulo %120
{p↑{e-f}}$; hence $λ$ is a divisor of$$ %121
λ(p↓1↑{e↓1} \ldots p↓t↑{e↓t}) = \mathop{\hjust{\rm lcm}}\left( %122
λ(p↓1↑{e↓1},\ldots,λ(p↓t↑{e↓t})\right).\eqno(9)$$ %123
%124
This algorithm in \MIX\ is simply$$ %125
\vcenter{\mixtwo{ %126
J6NN⊗*+2⊗\understep{A1. $j<0$?}\cr %127
STA⊗Z⊗\qquad$→Z$.\cr}}\eqno(7)$$ %128
That was on page 26. If we skip to page 49, $Y↓1 +\cdots+ Y↓k$ will %129
equal $n$ with probability$$ %130
\sum↓{\scriptstyle y↓1+\cdots+y↓k=n\atop\scriptstyle y↓1,\ldots,y↓k≥0} %131
\quad\prod↓{1≤s≤k} %132
{e↑{-np↓s}(np↓s)↑{y↓s}\over y↓s!} %133
={e↑{-n}n↑n\over n!}.$$ %134
This is not hard to express in terms of $n$-dimensional integrals,$$ %135
{{\int↓{α↓n}↑n \,dY↓n \int↓{α↓{n-1}}↑{Y↓n} %136
\,dY↓{n-1}\;\ldots\int↓{α↓1}↑{Y↓2}\,dY↓1} \over %137
{\int↓0↑n \,dY↓n \int↓0↑{Y↓n} \,dY↓{n-1}\;\ldots %138
\int↓0↑{Y↓2}\,dY↓1}},\qquad\hjust{where}\qquad α↓j= %139
\max(j-t,0).\eqno(24)$$ %140
This together with (25) implies that $$\def\rtn{\sqrt n} %141
\lim↓{n→∞} {s \over \rtn} %142
\sum↓{\rtn s<k≤n}{n\choose k}\left({k\over n} - {s\over \rtn}\right)↑k %143
\left({s\over\rtn} + 1 -{k \over n}\right)↑{n-k-1} = e↑{{-2s}↑2},\qquad s≥0, %144
\eqno(27)$$ a limiting relationship which appears to be quite difficult to %145
prove directly. %146
%147
\exbegin{EXERCISES---Special Set}\exno 17. [HM26] Let $t$ be a fixed real %148
number. For $0≤k≤n$, let$$P↓{nk}(x)=\int↑x↓{n-t}\,dx↓n\int↓{n-1-t}↑{x↓n}\, %149
dx↓{n-1}\;\,\ldots\int↓{k+1-t}↑{x↓{k+2}}\,dx↓{k+1}\int↓0↑{x↓{k+1}} %150
\,dx↓k\,\;\ldots\int↓0↑{x↓2}\,dx↓1;$$ %151
another way to write these integrals, although I don't use it in my book, is
\def\jnt{\int\limitswitch}$$P↓{nk}(x)=\jnt↑x↓{n-t}\,dx↓n\jnt↓{n-1-t}↑{x↓n}\, %149
dx↓{n-1}\;\,\ldots\jnt↓{k+1-t}↑{x↓{k+2}}\,dx↓{k+1}\jnt↓0↑{x↓{k+1}} %150
\,dx↓k\;\,\ldots\jnt↓0↑{x↓2}\,dx↓1.$$ %151
Eq. (24)\footnote*{Page 68.} is equal to$$\def\sumk{\sum↓{1≤k≤n}} %152
\sumk X↑\prime↓k Y↑\prime↓k \left/\sqrt{\sumk{X↑\prime↓k}↑2} %153
\sqrt{\sumk{Y↑\prime↓k}↑2}\right..$$\par %154
\runningrighthead{A BIG MATRIX DISPLAY} section{3.3.3.3} %155
\subsectionbegin{3.3.3.3. This subsection doesn't exist}Finally, look at page %156
91.$$\def\dgdts{\raise 6pt\hjust{.}\≥\raise 3pt\hjust{.}\≥.} %157
\def\5{\hskip5pt}
\eqalign{U⊗=\left(\vcenter{\halign{\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$} %158
\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗
\ctr{$ #$}\quad⊗\ctr{$ #$}\cr 1\cr ⊗\dgdts\cr ⊗⊗1\cr %159
\5c↓1\5⊗\ldots⊗\5c↓{k-1}\5⊗1⊗\5c↓{k+1}\5⊗\ldots⊗\5c↓n\5\cr %160
⊗⊗⊗⊗1\cr⊗⊗⊗⊗⊗\dgdts\cr⊗⊗⊗⊗⊗⊗1\cr}}\right),\cr %161
\noalign{\vskip 12pt}
U↑{-1}⊗=\left(\vcenter{\halign{\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$} %162
\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗
\ctr{$ #$}\quad⊗\ctr{$ #$}\cr 1\cr ⊗\dgdts\cr ⊗⊗1\cr %163
-c↓1⊗\ldots⊗-c↓{k-1}⊗1⊗-c↓{k+1}⊗\ldots⊗-c↓n\cr %164
⊗⊗⊗⊗1\cr⊗⊗⊗⊗⊗\dgdts\cr⊗⊗⊗⊗⊗⊗1\cr}}\right).\cr}\eqno(25)$$ %165
This ends the test data, fortunately T\hskip-1pt\lower1.94pt\hjust{E}\hskip-1pt
X is working fine.\par\vfill\eject %166